import java.util.Arrays;

//自己创建的堆
public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem =new int[10];//对数组初始化
    }


    //创建一个大根堆
    public void creatHeap(int[] array) {
        for(int i = 0; i < array.length; i++) {
            elem[i] = array[i];//将原始数据给到了elme数组
            //每次放入到一个元素usedSize记录一下
            usedSize++;
        }

        //对数组进行调整（向下调整）
        //因为每次都是从根往下调整

        for(int parent = usedSize - 1 - 1; parent >= 0; parent--) {
            //依次调成树
            shiftDown(parent,usedSize);//useadSize是一个结束条件
            //因为每次调整都需要将其子树进行调整，所以调整完最后的子树的子树下标都是大于usedSize的
        }

    }


    //len 代表每棵子树的结束位置
    //preant 代表每棵子树的根节点
    //向下调整
    //进行调整的条件：存在左孩子，因为这个是一个完全二叉树
    private void shiftDown(int parent,int len) {
        int child = 2 * parent + 1;//记录当前根的孩子的最大值的下标
        //因为是要对当前根的子树都要进行交换，所以是一个循环
        while(child < len) {
            //只有child小于数组的有效长度才说明存在左孩子
            //elem[child] < elem[child+1] 只有这个条件的时候说明 这里认为是一定存在右孩子
            //所以还需要加上一个条件 child + 1 < len,满足这个条件才说明存在右孩子
            //不满足这个条件会直接到49行，child就是当前的左孩子
            if(child + 1 < len && elem[child] < elem[child+1]) {
                child = child+1;
            }
            //来到这一步说明当前可以进行对根和孩子的最大值进行比较了
            if(elem[parent] < elem[child]) {
                //进行交换
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                //交换完一颗树之后还要进行下面的子树继续进行交换
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;//已经是大根堆了，直接跳出循环
            }

        }
    }

    //插入元素
    public void push(int val) {
        //检查是否满
        if(isFull()) {
            //进来了就说明当前已经满了，需要进行扩容
            elem = Arrays.copyOf(elem,2 * elem.length);
            //采取的二倍扩容
        }
        //进行插入
        elem[usedSize] = val;
        usedSize++;
        //调用向上调整
        shiftUP(usedSize - 1);//插入元素的下标
        //我们插入的元素是在原本就是一个大根堆（或者是小根堆）,所以只有只需要在插入元素的路径上进行调整，所以进行的是向上调整
    }

    //检查堆是否满了
    public boolean isFull() {
        return usedSize == elem.length;
    }


    public void shiftUP(int child) {
        int parent = (child - 1) / 2;//找到当前节点的父节点
        //开始调整
        //child = 0的时候表示根节点已经判断过了，所以就结束了
        while(child > 0) {
            if(elem[parent] < elem[child]) {
                //进行交换
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                child = parent;//交换完成之后child赋值当前的根节点，进行下一次的调整
                parent = (child - 1) / 2;//找到当前的根节点
            } else {
                break;//elem[parent] > elem[child]说明已经满足当前的大根堆(小根堆)了，所以直接跳出循环就可以了
            }
        }
    }

    public void poll() {
        //判断堆是否为空
        if(empty()) {
            //进来的话就说明这个是空堆
            //抛异常
            throw new HeapEmptyException("优先级队列是空的");
        }

        //0下标元素和最后一个下标元素进行交换
        int tmp = elem[0];
         elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;//交换完成之后就删除最后一个元素
        //进行向下调整
        shiftDown(0,usedSize-1);
    }

    public boolean empty() {
        return usedSize == 0;
    }

    public int peek() {
        //判空
        if(empty()) {
            throw new RuntimeException("优先级队列是空的！");
        }
        return elem[0];
    }



    //则总的时间复杂度是N*logN （N省略掉了）
    //堆排序，从小到大的排
    //建立大根堆:0(n）
    public void heapSort() {
        int end = usedSize-1;

        //这个循环的时间复杂度是N*logN
        while(end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            //交换完成
            //向下调整
            shiftDown(0,end);
            end--;
        }
    }
}
